package _interview100;

import _object.ListNode;

/**
 * 19. 删除链表的倒数第 N 个结点
 */
public class No19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sent = new ListNode(-1);
        sent.next = head;
        ListNode left = sent, right = sent;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return sent.next;
    }

    /**
     * 方法一：计算链表长度
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode sent = new ListNode(-1);
        sent.next = head;

        ListNode cur = sent;

        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }

        for (int i = 0; i < length - n; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;

        return sent.next;
    }

    /**
     * 方法二：双指针
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode sent = new ListNode(-1, head);
        ListNode cur = sent;

        int step = 0;
        while (head != null) {
            head = head.next;
            step++;
            if (step > n) {
                cur = cur.next;
            }
        }
        cur.next = cur.next.next;

        return sent.next;
    }
}
